/**
 * https://leetcode.cn/problems/number-of-provinces/submissions/573449836/
 * 547. 省份数量
 * medium,陈贝纯 2024.10.17
 * 并查集
 */

class Solution {
public:
    void pair(vector<int>& parent,int i,int j){
        parent[find(parent,j)]=find(parent,i);
    }
    int find(vector<int>& parent,int i){
        if(parent[i]!=i){
            parent[i]=find(parent,parent[i]);
        }
        return parent[i];
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        vector<int> parent(n);
        for(int i=0;i<n;++i)
            parent[i]=i;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(isConnected[i][j]==1)
                pair(parent,i,j);
            }
        }
        set<int>s;
        for(int i=0;i<n;++i)
            s.insert(find(parent,i));
        return s.size();
    }
};